<?php
class kisRandomMap{
    // Map Create
    private $_w;
    private $_h;
    private $_grids;
    private $_density;
    private $_ca_x;
    private $_ca_y;

    private $star = '*';    //地面
    private $sky = 0;       //墙

    private $_nodeSet;
    private $_nodeTmpSet;

    private $_runMode;

    private $_allRoadArr;   //所有节点集合之间的距离信息
    private $_selRoadArr;   //最终选用的节点集合连接路径

    // Construct
    public function kisRandomMap() {
        $this->_w = 6;
        $this->_h = 6;
        $this->_grids = array();
        $this->_density = 35;
        $this->_ca_x = 4;
        $this->_ca_y = 5;
        $this->_runMode = 0;
    }

    // 设置随机地图大小
    public function set($width = 6, $height = 6) {
        if ( $width > 0 && $width<1000) $this->_w = $width;
        if ( $height > 0 && $height<1000) $this->_h = $height;
        return $this;
    }

    // 设置随机地图密度
    public function setDensity($v) {
        // $v=M,    ==>  M%.
        // if($v<0 || $v>100) $v=45;
        // M% ==>  (M-5)% to (M+5)%   
        // $a = $v>5 ? ($v-5) : 0;
        // $b = $v<95 ? ($v+5) : 100;

        if($v>=0 && $v<=100) $this->_density = $v;
        return $this;
    }

    // 设置随机地图 CA X-Y
    public function setCA($x, $y) {
        if($x>=0 && $v<=100) $this->_ca_x = $x;
        if($y>=0 && $y<=100) $this->_ca_y = $y;
        return $this;
    }

    // 取到随机地图
    public function get() {
        return $this->_grids;
    }

    // 按照数据库信息恢复地图
    public function recoveryMap($jsonObj) {
        if($jsonObj )
            return $this->_recoveryByJson($jsonObj);
        return false;
    }

    // 
    public function getMapJsonObj() {
        return $this->_getJsonObj();
    }

    // 生成随机地图
    public function create() {
        $this->_init();
        $c = count($this->_grids);
        $p = ($c * $this->_density)/100;
        $this->_randStar($p);
        // $this->_cellularAutomata();
        return $this;
    }

    // 执行细胞自动机
    public function run_ca() {
        $this->_cellularAutomata();
        return $this;
    }

    // 执行细胞自动机
    public function reset_ca($x,$y,$v) {
        if($x && $y && $v){
            $this->setCA($x,$y);
        }
        $this->_cellularAutomata();
        return $this;
    }

    // DEBUG
    public function set_debug($v=1) {
        if($v){
            $this->_runMode = $v;
        }else{
            $this->_runMode = 0;
        }        
        return $this->_runMode;
    }

    // DEBUG
    public function debug_nodeSet() {
        return $this->_nodeSet;
    }

    // 最终选用的节点集合连接路径
    public function get_road() {
        return $this->_selRoadArr;
    }

    public function getRoadByNodeSet($nodeId,$nodeId2,$arr) {
        return $this->_getRoadByNodeSet($nodeId,$nodeId2,$arr);
    }
    
    // DEBUG
    public function debug_walk($debug=1) {
        if($debug===false){
            $lastMode = $this->_runMode;
            $this->_runMode=0;
            $ret = $this->_walk();
            $this->_runMode=$lastMode;
            return $ret;
        }
        return $this->_walk();
    }

    public function getNodeX($pos) {
        return $this->_getNodeX($pos);
    }

    public function getNodeY($pos) {
        return $this->_getNodeY($pos);
    }

    //设置随机地牢grids
    public function set_grids($grids) {
        return $this->_set_grids($grids);
    }

    /**
    |---------------------------------------------------------------
    | 生成随机地图的系列函数
    |---------------------------------------------------------------
    */
    private function _walk() {
/* 
判定两点间能够连接:
    如果两个点处于同一个集合则不能相连
    如果两点连线覆盖到另一点则不能相连
    如果两点连线交叉到已有线段则不能相连

算法定义:
    1）每个独立的节点为一个独立的集合
    2）计算所有能够连接的点和他们之间的距离
    3）在距离最短的备选边中选择一条最短的
    4）将其两点连接，归并到同一集合
    5）重复到2，直到空间中只有唯一一个集合
*/
        
        $this->_nodeSet=$this->_getNodeSet();

        $tmpNodeSet = array();    //tmp节点集合
        $tmpLinkSet = array();    //节点集合连接
        $roadArr = array('from' =>0 , 'to'=>0, 'distance'=>0);

        $tmpNodeSet = $this->_nodeSet;

        // $l = count($this->_grids);
        // $road='r';

        $tmpNodeSet = $this->_mergeTwoNodeSetByMinDistance();

        $this->_nodeTmpSet = $tmpNodeSet;

        return $this->_nodeTmpSet;
    }

    private function _mergeTwoNodeSetByMinDistance(){
/* 
判定两点间能够连接:
    如果两个点处于同一个集合则不能相连
    如果两点连线覆盖到另一点则不能相连
    如果两点连线交叉到已有线段则不能相连

算法定义:
    1）每个独立的节点为一个独立的集合
    2）计算所有能够连接的点和他们之间的距离
    3）在距离最短的备选边中选择一条最短的
    4）将其两点连接，归并到同一集合
    5）重复到2，直到空间中只有唯一一个集合
*/

        $tmpNodeSet = $this->_nodeTmpSet;
        $this->_allRoadArr = array();    //所有节点集合之间的距离信息
        $this->_selRoadArr = array();    //最终选用的节点集合连接路径
        $tmpMinLinkSet = array();
        $roadArr = array('from' =>0 , 'to'=>0, 'distance'=>0);

        //完成所有合并，直到只剩下唯一一个集合
        $len = count($tmpNodeSet);
        for ($i=0; $i <$len ; $i++) { 
            $tmpNodeSet = $this->_mergeTwoNodeSetByMinDistanceSub($tmpNodeSet);
            if(count($tmpNodeSet)<2){
                break;
            }
        }        

        return $tmpNodeSet;
    }

    private function _recoveryByJson($jsonObj){
        $map=array();
        if(isset($jsonObj['_w'])) $this->_w = $jsonObj['_w'];
        if(isset($jsonObj['_h'])) $this->_h = $jsonObj['_h'];
        if(isset($jsonObj['_grids'])) $this->_grids = $jsonObj['_grids'];
        if(isset($jsonObj['_density'])) $this->_density = $jsonObj['_density'];
        if(isset($jsonObj['_ca_x'])) $this->_ca_x = $jsonObj['_ca_x'];
        if(isset($jsonObj['_ca_y'])) $this->_ca_y = $jsonObj['_ca_y'];

        if(isset($jsonObj['star'])) $this->star = $jsonObj['star'];
        if(isset($jsonObj['sky'])) $this->sky = $jsonObj['sky'];
        if(isset($jsonObj['_nodeSet'])) $this->_nodeSet = $jsonObj['_nodeSet'];
        if(isset($jsonObj['_nodeTmpSet'])) $this->_nodeTmpSet = $jsonObj['_nodeTmpSet'];
        if(isset($jsonObj['_runMode'])) $this->_runMode = $jsonObj['_runMode'];
        if(isset($jsonObj['_allRoadArr'])) $this->_allRoadArr = $jsonObj['_allRoadArr'];
        if(isset($jsonObj['_selRoadArr'])) $this->_selRoadArr = $jsonObj['_selRoadArr'];
        if(isset($jsonObj['_runMode'])) $this->_runMode = $jsonObj['_runMode'];

        $map = $this->_getJsonObj();
        return $map;
    }

    private function _getJsonObj(){
        $jsonObj=array();
        $jsonObj['_w'] = $this->_w;
        $jsonObj['_h'] = $this->_h;
        $jsonObj['_grids'] = $this->_grids;
        $jsonObj['_density'] = $this->_density;
        $jsonObj['_ca_x'] = $this->_ca_x;
        $jsonObj['_ca_y'] = $this->_ca_y;

        $jsonObj['star'] = $this->star;
        $jsonObj['sky'] = $this->sky;
        $jsonObj['_nodeSet'] = $this->_nodeSet;
        $jsonObj['_nodeTmpSet'] = $this->_nodeTmpSet;
        $jsonObj['_runMode'] = $this->_runMode;
        $jsonObj['_allRoadArr'] = $this->_allRoadArr;
        $jsonObj['_selRoadArr'] = $this->_selRoadArr;
        $jsonObj['_runMode'] = $this->_runMode;
        return $jsonObj;
    }

    private function _mergeTwoNodeSetByMinDistanceSub($tmpNodeSet){
        //完成所有合并，直到只剩下唯一一个集合
        
        //$tmpNodeSet       //节点集合
        //$lastRoadArr      //上一次选用的路径信息

        $tmpAllLinkSet = $this->_allRoadArr;   //所有节点集合之间的距离信息
        $tmpLinkSet    = $this->_selRoadArr;   //最终选用的节点集合连接路径

        if(count($tmpLinkSet)==0){
            $firstRun=true;
        }else{
            $firstRun=false;
        }

        $min=0;
        $roadArr = array('from' =>0 , 'to'=>0, 'distance'=>0);

        if($firstRun){
            foreach ($tmpNodeSet as $nodeId => $nodeArr) {
                foreach ($tmpNodeSet as $nodeId2 => $nodeArr2) {
                    if($nodeId!=$nodeId2){
                        $d = $this->_getDistanceByNodeSet($nodeId,$nodeId2);
                        if($d!==false){
                            array_push($tmpAllLinkSet, 
                                    array('from' =>$nodeId , 'to'=>$nodeId2, 'distance'=>$d));
                            // if($this->_runMode){
                            //     echo 'DEBUG: '.__FUNCTION__.'() Distance:'.$d.',#'.$nodeId.'-#'.$nodeId2.PHP_EOL;
                            // }
                            if($d<$min || $min===0){
                                $min = $d;
                                $roadArr['from']=$nodeId;
                                $roadArr['to']=$nodeId2;
                            }                        
                        }
                    }
                }
            }
        }else{
            $lastRoadArr=end($tmpLinkSet);
            foreach ($tmpNodeSet as $nodeId => $nodeArr) {
                $nodeId2 =$lastRoadArr['to'];
                if(isset($tmpNodeSet[$nodeId2])){
                    if($nodeId!=$nodeId2){
                        $d = $this->_getDistanceByNodeSet($nodeId,$nodeId2);
                        if($d!==false){
                            array_push($tmpAllLinkSet, 
                                    array('from' =>$nodeId , 'to'=>$nodeId2, 'distance'=>$d));
                            // if($this->_runMode){
                            //     echo 'DEBUG: '.__FUNCTION__.'() Distance#2:'.$d.',#'.$nodeId.'-#'.$nodeId2.PHP_EOL;
                            // }
                        }
                    }
                }
            }
            // $min=0;
            foreach ($tmpAllLinkSet as $key => $value) {
                $d = $value['distance'];
                if($d<$min || $min===0){
                    $min = $d;
                    $roadArr['from']=$nodeId;
                    $roadArr['to']=$nodeId2;
                } 
            }
            // not firstRun code end.
        }


        //在距离最短的备选边中选择一条最短的
        $tmpMinLinkSet = array();
        foreach ($tmpAllLinkSet as $tmpRoadArr) {
            if($tmpRoadArr['distance']==$min){
                array_push($tmpMinLinkSet,$tmpRoadArr);
            }
        }
        $n = $this->_rnd(0, count($tmpMinLinkSet) -1 );
        $roadArrMin=$tmpMinLinkSet[$n];
        array_push($tmpLinkSet,$roadArrMin);

        $tmpNodeSet = $this->_mergeTwoNodeSet($tmpNodeSet,$roadArrMin['from'],$roadArrMin['to']);
        // if($this->_runMode){
        //     echo 'DEBUG: '.__FUNCTION__.'() result:'.$d.',#'.$nodeId.'-#'.$nodeId2.PHP_EOL;
        // }

        //清除掉已经合并的
        foreach ($tmpAllLinkSet as $key => $tmpRoadArr) {
            if($tmpRoadArr['from']==$roadArrMin['from'] || $tmpRoadArr['to']==$roadArrMin['from']){
                unset($tmpAllLinkSet[$key]);
            }elseif ($tmpRoadArr['from']==$roadArrMin['to'] || $tmpRoadArr['to']==$roadArrMin['to']){
                unset($tmpAllLinkSet[$key]);
            }
        }

        $this->_allRoadArr = $tmpAllLinkSet;   //所有节点集合之间的距离信息
        $this->_selRoadArr = $tmpLinkSet;   //最终选用的节点集合连接路径

        return $tmpNodeSet;
    }

    private function _mergeTwoNodeSet($tmpNodeSet,$lastSetId,$curSetId){
        if($lastSetId===$curSetId) return $tmpNodeSet;
        if(!isset($tmpNodeSet[$lastSetId])) return $tmpNodeSet;
        $delArr = $tmpNodeSet[$lastSetId];
        // if($this->_runMode) {
        //     echo 'DEBUG: '.__FUNCTION__.'() #'.$lastSetId.',#'.$curSetId.PHP_EOL;
        //     echo '--del,'.implode(',',$delArr) .PHP_EOL; 
        //     echo '--append,'.implode(',',$tmpNodeSet[$curSetId]) .PHP_EOL; 
        // }
        if(is_array($delArr)){
            foreach ($delArr as $moveNode) {
                if($moveNode && is_array($tmpNodeSet[$curSetId]))
                    array_push($tmpNodeSet[$curSetId], $moveNode);
            }
            unset($tmpNodeSet[$lastSetId]);
        }
        return $tmpNodeSet;
    }

    private function _getDistanceByNodeSet($nodeSetId1,$nodeSetId2){
        $roadArr = $this->_getRoadByNodeSet($nodeSetId1,$nodeSetId2,$this->_nodeTmpSet);
        return $roadArr['distance'];
    }

    private function _getRoadByNodeSet($nodeSetId1,$nodeSetId2,$setArr){
        $roadArr = array('from' =>0 , 'to'=>0, 'distance'=>0);
        // if($this->_runMode){
        //     echo 'DEBUG: '.__FUNCTION__.'('.$nodeSetId1.','.$nodeSetId2.',)'.PHP_EOL;
        // }
        // if($setArr===false){
        //     $setArr=$this->_nodeTmpSet;
        //     // if($this->_runMode){
        //     //     echo 'DEBUG: '.__FUNCTION__.'() use this->_nodeTmpSet!'.PHP_EOL;
        //     // }
        // }else{
        //     var_dump($setArr);
        // }

        if(isset($setArr[$nodeSetId1])){
            $nodeSet1 = $setArr[$nodeSetId1];
        }else{
            if($this->_runMode){
                echo 'DEBUG: '.__FUNCTION__.'() #'.$nodeSetId1.' not set!'.PHP_EOL;
            }
            return false;
        }
        if(isset($setArr[$nodeSetId2])){
            $nodeSet2 = $setArr[$nodeSetId2];
        }else{
            if($this->_runMode){
                echo 'DEBUG: '.__FUNCTION__.'() #'.$nodeSetId2.' not set!'.PHP_EOL;
            }
            return false;
        }
        $min = 0;
        foreach ($nodeSet1 as $pos1) {
            foreach ($nodeSet2 as $pos2) {
                $d =$this->_getDistanceByNode($pos1,$pos2);
                if($d<$min || $min === 0){
                    $min = $d;
                    $roadArr['from']=$pos1;
                    $roadArr['to']=$pos2;
                    $roadArr['distance']=$min;
                }
            }
        }
        return $roadArr;
    }

    private function _getDistanceByNode_v1($pos1,$pos2){
        return abs($this->_getNodeX($pos1)-$this->_getNodeX($pos2))+abs($this->_getNodeY($pos1)-$this->_getNodeY($pos2));
    }
	
	private function _getDistanceByNode($pos1,$pos2){
		$a = $this->_getNodeX($pos1)-$this->_getNodeX($pos2);
		$b = $this->_getNodeY($pos1)-$this->_getNodeY($pos2);
        return $a*$a + $b*$b;
    }

    private function _getNodeX($pos) {
        return fmod($pos,$this->_w);
        // $y = intval($pos/$this->_w);

    }

    private function _getNodeY($pos) {
        // $x = fmod($pos,$this->_w);
        return intval($pos/$this->_w);
    }

    private function _getNodeSet() {
/* 
能连上的节点，放入同一个节点集合.
*/
        $this->_nodeSet = array();    //原始节点集合
        $this->_nodeTmpSet = array();    //tmp节点集合

        $l = count($this->_grids);
        $road='r';

        //首行
        for ($i=0; $i <$this->_w ; $i++) { 
            // $wc = $this->_checkAroundStarCountSub($i,$this->star,0);            
            // if ($wc>0) {
            if($this->_grids[$i] === $this->star){
                $len2=count($this->_nodeTmpSet);
                $flag = false;
                if($len2>0)
                for ($ii=0; $ii<$len2 ; $ii++) { 
                    $bb = $i-1;     //左侧那一个节点
                    if( in_array($bb,$this->_nodeTmpSet[$ii],true)) {
                        array_push($this->_nodeTmpSet[$ii], $i);
                        $flag = true;
                        break;
                    }
                }
                if($flag===false){
                    $tmpArr = array();
                    array_push($tmpArr,$i);
                    array_push($this->_nodeTmpSet, $tmpArr);
                }
            }
        }
        $this->_nodeSet = $this->_nodeTmpSet ;

        //其他行
        for ($i=$this->_w; $i <$l ; $i++) { 
            // $wc = $this->_checkAroundStarCountSub($i,$this->star,0);
            // if ($wc>0){
            if($this->_grids[$i] === $this->star){
                $upwc = $this->_checkUpperAndLeftStarCount($i,$this->star,0);
                if($upwc>0){
                    $this->_addToSet($i);
                }else{
                    // if($this->_runMode){
                    //     echo 'DEBUG: '.__FUNCTION__.'() #'.$i.'--newArr'.PHP_EOL;
                    // }
                    $tmpArr = array();
                    array_push($tmpArr,$i);
                    array_push($this->_nodeTmpSet, $tmpArr);
                }
            }

        }
        return $this->_nodeTmpSet;
    }

    private function _isInNodeSet($tmpNode,$_nodeTmpSet) {
        if(!$tmpNode) return false;
        if(is_array($_nodeTmpSet)){
            foreach ($_nodeTmpSet as $nodeSetId => $nodeSetArr) {
                if($nodeSetArr)
                if( in_array($tmpNode,$nodeSetArr,true)){
                    return $nodeSetId;
                }
            }
        }        
        return false;
    }

    private function _addToSet($pos) {
        $len=count($this->_nodeTmpSet);
        $tmpPos = $pos-$this->_w;
        $checkArr = array();
        for ($j=$tmpPos-1; $j<=$tmpPos+1 ; $j++) {  //上面的
            array_push($checkArr, $j);
        }
        array_push($checkArr, $pos-1);  //左侧的
        // if($this->_runMode){
        //     echo 'DEBUG: '.__FUNCTION__.'() #'.$pos.PHP_EOL;
        //     echo '--checkArr:'.implode(',',$checkArr) .PHP_EOL;
        // }        
        $lc=count($checkArr);
        $hitArr=array();        //存放检测后命中的集合id
        for ($j=0; $j<$lc ; $j++) { 
            $tmpNode = $checkArr[$j];
            if($tmpNode>=0){
                $i = $this->_isInNodeSet($tmpNode,$this->_nodeTmpSet);
                if( $i!==false ){
                    array_push($hitArr, $i);
                    // if($this->_runMode) {
                    //     echo 'DEBUG: '.__FUNCTION__.'() #'.$pos.PHP_EOL;
                    //     echo '--tmpNode,'.$tmpNode .PHP_EOL; 
                    //     echo '--hit array,'.implode(',',$this->_nodeTmpSet[$i]) .PHP_EOL; 
                    // }
                }
            }
        }

        // if($this->_runMode) {
        //     echo '--hitArr item,'.implode(',',$hitArr) .PHP_EOL; 
        // }
        $hitArr=array_unique($hitArr);
        // if($this->_runMode) {
        //     echo '--hitArr new item,'.implode(',',$hitArr) .PHP_EOL; 
        // }

        $hitLen=count($hitArr);
        $lastSetId=null;
        $curSetId=null;
        if($hitLen){
            foreach ($hitArr as $hitId => $hitSetId) {
                if($lastSetId===null){
                    $lastSetId = $hitSetId;
                }else{
                    $curSetId = $hitSetId;
                    $delArr = $this->_nodeTmpSet[$curSetId];
                    if($this->_runMode) {
                        echo 'DEBUG: '.__FUNCTION__.'() #'.$pos.PHP_EOL;
                        echo '--del,'.implode(',',$delArr) .PHP_EOL; 
                        echo '--append,'.implode(',',$this->_nodeTmpSet[$lastSetId]) .PHP_EOL; 

                        echo '-- lastSetId='.$lastSetId .PHP_EOL; 
                        echo '-- i=,'.$curSetId .PHP_EOL; 

                    }
                    array_push($this->_nodeTmpSet[$lastSetId], $pos);
                    foreach ($delArr as $moveNode) {
                        array_push($this->_nodeTmpSet[$lastSetId], $moveNode);
                    }
                    unset($this->_nodeTmpSet[$curSetId]);
                    $lastSetId=$curSetId;
                }
            }
            if($curSetId===null){
                array_push($this->_nodeTmpSet[$lastSetId], $pos);
            }
        }else{
            $tmpArr = array();
            array_push($tmpArr,$pos);
            array_push($this->_nodeTmpSet, $tmpArr);
        }

        return false;
    }

    private function _randStar($starCount) {
        if($this->_runMode) echo 'DEBUG: ' . __FUNCTION__ . '() starCount='.$starCount. PHP_EOL; 
        if(!$starCount) return false;
        $l = count($this->_grids);
        if($starCount>=$l) return false;        
        // $star = '*';
        for ($i=0; $i <$starCount ; $i++) { 
            $tmpPos = $this->_rnd(0, count($this->_grids) -1 );
            $kk=1;

            while (! $this->_checkPosVal($tmpPos,$this->star)) {
                $tmpPos = $this->_rnd(0, count($this->_grids) -1 );
                if($kk++>$starCount){
                    if($this->_runMode) echo 'DEBUG: ' . __FUNCTION__ . '() break !'. PHP_EOL; 
                    $kk=-1;
                    break;
                }
            }
            if(isset($this->_grids[$tmpPos]) && $kk>0){
                $this->_grids[$tmpPos] = $this->star;
            }
        }
        return $this;
    }

    //Cellular Automata – 细胞自动机
    private function _cellularAutomata() {
        /* 浏览数组中每个格子
        *  统计当前格子周围八个格子的“墙”的数量
        *  如果墙数小于X值，就将当前格设为“地面”
        *  如果墙数大于Y值，就将当前格设为“墙”
        *  如果在X-Y之间，则当前格保持不变
        *  实际生成中我们取4-5的模型
        */
        // $star = '*';
        // $sky = 0;
        $l = count($this->_grids);
        
        for ($i=0; $i <$l ; $i++) { 
            $wc = $this->_checkAroundStarCount($i,$this->sky,false);
            if($wc<$this->_ca_x) {
                $val = $this->star ;
            }else if ($wc>$this->_ca_y){
                $val = $this->sky ;
            }else{
                $val = false;
            }
            if($val!==false) $this->_grids[$i] = $val;
        }        
        return $this;
    }

    private function _checkAroundStarCountSub($pos,$val,$opt) {
        // $miss_node = 1;
        $count = 0;
        if ($pos>=0 && isset($this->_grids[$pos])){
            if( $this->_grids[$pos] === $val) $count++;
        }else{
            // $count += $miss_node;
            if($opt===false){
                $count += $this->_rnd(0,1);
            }else{
                $count += $opt;
            }
        }
        return $count;
    }

    private function _checkAroundStarCount($pos,$val,$opt=false) {
        $count=0;        
        $tmpPos = $pos-$this->_w;
        $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);
        
        $tmpPos = $tmpPos-1;
        $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);
        $tmpPos = $tmpPos+2;
        $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);

        $tmpPos = $pos-1;
        $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);
        $tmpPos = $pos+1;
        $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);

        $tmpPos = $pos+$this->_w;
        $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);
        $tmpPos = $tmpPos-1;
        $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);
        $tmpPos = $tmpPos+2;
        $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);

        return $count;
    }

    private function _checkUpperAndLeftStarCount($pos,$val,$opt=false) {//检查上方和左侧是否有对应的集合($val)
        $disableTheLeftAndRightThrough=true;    //禁止左边界自动联通到右边界
        // if($this->_runMode) echo 'DEBUG: ' . __FUNCTION__ . '() #'.$pos. PHP_EOL; 

        $count=0;        
        $tmpPos = $pos-$this->_w;   //正上方
        $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);
        
        $rowId = intval(($pos+1)/$this->_w);

        if($disableTheLeftAndRightThrough){
            $tmpPos = $tmpPos-1;        //左上方
            if(fmod($pos,$this->_w)!=0 && $rowId == intval(($tmpPos+1)/$this->_w)){
                // if($this->_runMode) echo 'DEBUG: ' . __FUNCTION__ . '() left up #'.$tmpPos. PHP_EOL; 
                $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);
            }else{

            }

            $tmpPos = $tmpPos+2;        //右上方
            if(fmod($pos,$this->_w)!=($this->_w-1) &&$rowId == intval(($tmpPos+1)/$this->_w)){
                // if($this->_runMode) echo 'DEBUG: ' . __FUNCTION__ . '() right up #'.$tmpPos. PHP_EOL; 
                $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);
            }

            $tmpPos = $pos-1;           //left
            $a = fmod($pos,$this->_w);
            $b = intval(($tmpPos+1)/$this->_w);
            if($this->_runMode) echo 'DEBUG: ' . __FUNCTION__ . '() a='.$a. PHP_EOL;
            if($this->_runMode) echo 'DEBUG: ' . __FUNCTION__ . '() b='.$b. PHP_EOL;
            if($this->_runMode) echo 'DEBUG: ' . __FUNCTION__ . '() rowId='.$rowId. PHP_EOL;
            if(fmod($pos,$this->_w)!=0 && $rowId == intval(($tmpPos+1)/$this->_w)){
                if($this->_runMode) echo 'DEBUG: ' . __FUNCTION__ . '() left #'.$tmpPos. PHP_EOL; 
                $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);
            }
        }else{

            $tmpPos = $tmpPos-1;        //左上方
            $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);

            $tmpPos = $tmpPos+2;        //右上方
            $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);

            $tmpPos = $pos-1;           //left        
            $count += $this->_checkAroundStarCountSub($tmpPos,$val,$opt);
        }

        return $count;
    }
    
    private function _checkPosVal($pos,$val) {
        if ( isset($this->_grids[$pos]) && $this->_grids[$pos] == $val) return true;
        return false;
    }

    private function _isRepeating($p) {
        $l = count($this->_walkHistory);
		for ($i = 0; $i < $l; $i ++) {
			if ($this->_walkHistory[$i] == $p) return true;
		}
        $l = count($this->_walkHistory2);
		for ($i = 0; $i < $l; $i ++) {
			if ($this->_walkHistory2[$i] == $p) return true;
		}
		return false;
    }



    private function _getNext0() {
        $l = count($this->_grids);

        for ($i = 0; $i <= $l; $i++ ) {
            if ( isset($this->_grids[$i]) && $this->_grids[$i] == 0) return $i;
        }
        return -1;
    }

    private function _init() {
		$this->_grids = array();
		for ($y = 0; $y < $this->_h; $y ++) {
			for ($x = 0; $x < $this->_w; $x ++) {
				array_push($this->_grids, 0);
			}
        }
		return $this;
    }

    private function _rnd($min,$max) {
        return mt_rand($min,$max);
    }

    /**
    |---------------------------------------------------------------
    | 生成随机地牢地图的系列函数
    |---------------------------------------------------------------
    */

    private function _set_grids($grids) {       /* 生成随机地牢grids */
        $this->_grids=$grids;
        return $this->_grids;
    }


    
}


